package day_2022_12_to_3.year2023;

/**
 * @author haomin
 * @date 2023/03/08 23:06
 **/
public class Day3_8_Num45 {
    class Solution {
        public int maxValue(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            for(int i = 1; i < m; ++i) grid[i][0] = grid[i][0] + grid[i-1][0];
            for(int i = 1; i < n; ++i) grid[0][i] = grid[0][i] + grid[0][i-1];

            for(int i = 1; i < m; ++i) {
                for(int j = 1; j < n; ++j) {
                    grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
                }
            }
            return grid[m-1][n-1];
        }
    }
}